/*
 * @Author: szx
 * @Date: 2022-02-04 14:18:32
 * @LastEditTime: 2022-02-04 16:09:03
 * @Description:
 * @FilePath: \leetcode\900-999\912\912.js
 */
/**
 * @param {number[]} nums
 * @return {number[]}
 */
// 调库
var sortArray = function (nums) {
    nums.sort((a, b) => a - b);
    return nums;
};

// 冒泡
var sortArray = function (nums) {
    const n = nums.length;
    for (let i = 0; i < n - 1; i++) {
        for (let j = 1; j < n - i; j++) {
            if (nums[j - 1] > nums[j]) {
                const tmp = nums[j];
                nums[j] = nums[j - 1];
                nums[j - 1] = tmp;
            }
        }
    }
    return nums;
};

// 选择排序
var sortArray = function (nums) {
    const n = nums.length;
    for (let i = 0; i < n - 1; i++) {
        let min = i;
        for (let j = i + 1; j < n; j++) {
            if (nums[j] < nums[min]) {
                min = j;
            }
        }
        if (min != i) {
            [nums[i], nums[min]] = [nums[min], nums[i]];
        }
    }
    return nums;
};

// 插入排序
var sortArray = function (nums) {
    const n = nums.length;
    for (let i = 1; i < n; i++) {
        let flag = nums[i];
        let j = i - 1;
        while (j >= 0 && flag < nums[j]) {
            nums[j + 1] = nums[j];
            j--;
        }
        nums[j + 1] = flag;
    }
    return nums;
};

// 希尔排序
var sortArray = function (nums) {
    const n = nums.length;
    // 直接用证明
    let h = 1;
    while (h < n / 3) {
        h = 3 * h + 1;
    }
    while (h > 0) {
        for (let i = h; i < n; i++) {
            let flag = nums[i];
            let j = i - h;
            while (j >= 0 && flag < nums[j]) {
                nums[j + h] = nums[j];
                j-h;
            }
            nums[j + h] = flag;
        }
        h = Math.floor(h / 3);
    }
    return nums;
};


console.log(sortArray([5, 2, 3, 1]));
